#include<bits/stdc++.h>
#define int long long 
using namespace std;

inline int read() {
	int x = 0, f = 0; char ch = getchar();
	while(ch < '0' or ch > '9') f |= (ch == '-'), ch = getchar();
	while(ch >= '0' and ch <= '9') x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
	return f ? -x : x;
}
int __stk[128], __top;
inline void write(int x) {
    if(x < 0) putchar('-'), x = -x;
	do { __stk[++__top] = x % 10, x /= 10; } while(x);
	while (__top) putchar(__stk[__top--] + '0');
}
bool stmer;
int T, n, m, mod;
void add(int &x, int y) { (x += y) >= mod and (x -= mod); }
void mul(int &x, int y) { x = x * y % mod; }
int q_pow(int x, int k) {
    int res = 1;
    for(; k; k >>= 1, mul(x, x))
        if(k & 1) mul(res, x);
    return res;
}
int f[5000000];
void solve() {
    f[0] = 1;
    n = read(), m = read();
    
    for(int i = 1; i <= n; i++) {
        int sum = 0;
        for(int j = 0; j <= m; j++) add(sum, f[i * m - j]);
        for(int j = i * m; j + 1; j--) {
            add(sum, mod - f[j]), add(f[j], sum);
            if(j > m) add(sum, f[j - m - 1]);
        }
    }
    int ans = 0;
    for(int i = 0; i <= n * m; i++) add(ans, f[i] * f[i] % mod), f[i] = 0;
    ans = (mod + 1 - ans * q_pow(m + 1, 2 * n * (mod - 2) % (mod - 1)) % mod) * ((mod + 1) / 2) % mod;
    write(ans), putchar('\n');
    // for(int i = 0; i <= n * m; i++) cout << f[i] << " ";
    // cout << '\n';
}
bool edmer;
signed main() {
	freopen("pr.in", "r", stdin);
	freopen("pr.out", "w", stdout);
	cerr << "[Memory] " << (&stmer - &edmer) / 1024 / 1024 << " MB\n";
    mod = read(), T = read(); while(T--) solve();

    cerr << "[Runtime] " << (double) clock() / CLOCKS_PER_SEC << " seconds";
	return 0;
} 